import heapq

class Node:
    def __init__(self, level, current_weight, current_value, bound):
        self.level = level          # 当前决策的物品层级
        self.current_weight = current_weight  # 当前总重量
        self.current_value = current_value    # 当前总价值
        self.bound = bound          # 该分支的上界（最大价值估计）
    
    # 优先队列按 bound 从大到小排序（最大堆）
    def __lt__(self, other):
        return self.bound > other.bound

def bound(node, N, W, weights, values, sorted_items):
    if node.current_weight >= W:
        return 0  # 超重，上界为 0
    
    bound_value = node.current_value
    j = node.level + 1
    total_weight = node.current_weight
    
    # 贪心估算剩余物品能装的最大价值（按价值密度排序）
    while j < N and total_weight + sorted_items[j][0] <= W:
        total_weight += sorted_items[j][0]
        bound_value += sorted_items[j][1]
        j += 1
    
    # 如果还有剩余物品，但装不下全部，则装部分（分数背包思路，但 0-1 背包只能取整数）
    if j < N:
        bound_value += (W - total_weight) * (sorted_items[j][1] / sorted_items[j][0])
    
    return bound_value

def knapsack_branch_and_bound(W, weights, values, N):
    # 按价值密度（value/weight）从高到低排序物品
    sorted_items = sorted(zip(weights, values), key=lambda x: x[1]/x[0], reverse=True)
    weights_sorted = [x[0] for x in sorted_items]
    values_sorted = [x[1] for x in sorted_items]
    
    max_value = 0
    best_solution = []
    
    # 优先队列（最大堆，按 bound 从大到小）
    queue = []
    
    # 初始节点（未选任何物品）
    root = Node(-1, 0, 0, 0)
    root.bound = bound(root, N, W, weights_sorted, values_sorted, sorted_items)
    heapq.heappush(queue, root)
    
    while queue:
        current_node = heapq.heappop(queue)
        
        # 如果当前节点的上界 <= 已知最优解，剪枝
        if current_node.bound <= max_value:
            continue
        
        # 如果已经决策完所有物品
        if current_node.level == N - 1:
            continue
        
        next_level = current_node.level + 1
        
        # 1. 选择下一个物品（选）
        new_weight = current_node.current_weight + weights_sorted[next_level]
        new_value = current_node.current_value + values_sorted[next_level]
        
        if new_weight <= W and new_value > max_value:
            max_value = new_value
            best_solution = [next_level]  # 记录选择的物品索引（需映射回原顺序）
        
        # 计算选择该物品后的上界
        if new_weight <= W:
            new_node = Node(next_level, new_weight, new_value, 0)
            new_node.bound = bound(new_node, N, W, weights_sorted, values_sorted, sorted_items)
            if new_node.bound > max_value:
                heapq.heappush(queue, new_node)
        
        # 2. 不选择下一个物品（不选）
        new_node = Node(next_level, current_node.current_weight, current_node.current_value, 0)
        new_node.bound = bound(new_node, N, W, weights_sorted, values_sorted, sorted_items)
        if new_node.bound > max_value:
            heapq.heappush(queue, new_node)
    
    return max_value

# 示例
W = 10
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
N = len(weights)
max_val = knapsack_branch_and_bound(W, weights, values, N)
print("最大价值（分支限界法）:", max_val)  # 输出 10